package com.vincent.algorithms.sort;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 若将两个有序表合并成一个有序表，称为2-路归并
 *
 * 平均时间复杂度O(nlog₂n)
 * 最好和最坏时间复杂度也同样是O(nlog₂n)
 *
 * 空间复杂度O(n) 需借助辅助空间
 * 稳定性 稳定
 *
 * java.util.Collections 的sort方法默认就是根据长度判断排序方法 插入排序  归并排序
 * 对于归并排序 还提供了TimSort 这是一个大量优化过的归并排序，对归并排序排在已经反向排好序的输入时表现O(n^2)的特点做了特别优化。
 * 对已经正向排好序的输入减少回溯。对两种情况混合（一会升序，一会降序）的输入处理比较好
 *
 *
 *
 * Created by yangwenchang on 2017/8/23.
 */
public class MergeSort implements Sort{

    public static int sum = 0;
    @Override
    public <T> void sort(T[] array, Comparator<? super T> c) {

    }

    public static  <T> void sortMerge(T[] array,T[] tmp,int start,int end, Comparator<? super T> c){
        if (start < end) {
            int mid = (start + end) / 2;
            sortMerge(array,tmp, start, mid,c);// 左边有序
            sortMerge(array,tmp, mid + 1, end,c);// 右边有序
            merge(array,tmp, start, mid, end,c);
        }
    }


    public static <T> void merge(T[] array,T[] tmp, int start, int mid, int end, Comparator<? super T> c) {
        int left = start;
        int right = mid + 1;

        int index = 0;
//        依次用两个有序段 里选出较小的部分放入辅助空间
        for (; left <= mid && right <= end; ) {

            if (c.compare(array[left], array[right]) <= 0) {
                tmp[index++] = array[left++];
            } else {
                tmp[index++] = array[right++];
            }
        }

        while (left <= mid) {
            tmp[index++] = array[left++];
        }

        while (right <= end) {
            tmp[index++] = array[right++];
        }

//        把有序的值从辅助空间 copy 到 原数组
//        这里建议不要手动复制 系统提供了数组复制函数的native实现 更高效
        System.arraycopy(tmp,0,array,start,end-start+1);
//        int temp = start;
//        int i = 0;
//        while (temp <= end) {
//            array[temp++] = tmp[i++];
//        }
        System.out.println(Arrays.asList(tmp));
    }

    public static void main(String[] args) {

        Integer[] arr = {89,5,45,23,2,1,60,9,6,100};
        System.out.println(Arrays.asList(arr));

        Integer[] tmp = new Integer[arr.length];
        MergeSort.sortMerge(arr,tmp,0,arr.length-1,(x,y)->x-y);
        System.out.println(Arrays.asList(arr));

    }
}
